lis（最长上升子序列）和lcs（最长公共子序列）是经典的题目。
用dp的方法是n^2的。
lis：
定义d[k]:长度为k的上升子序列的最末元素，若有多个长度为k的上升子序列，则记录最小的那个最末元素。
注意d中元素是单调递增的，下面要用到这个性质。
首先len = 1,d[1] = a[1],然后对a[i]:若a[i]>d[len]，那么len++，d[len] = a[i];
否则，我们要从d[1]到d[len-1]中找到一个j，满足d[j-1]
Lis and Lcs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
const int maxn=100010;
int n,a[maxn],b[maxn],f[maxn],stack[maxn],top;
void find(int x){
int l=0,r=top,ans;
while(l<=r){
int mid=l+r>>1;
if(stack[mid]<x)ans=mid,l=mid+1;
else r=mid-1;
}
stack[ans+1]=x;
}
int main() {
scanf("%d",&n);
for(re int i=1; i<=n; i++)scanf("%d",&a[i]),f[a[i]]=i;
for(re int i=1; i<=n; i++)scanf("%d",&b[i]),b[i]=f[b[i]];
for(re int i=1; i<=n; i++) {
if(stack[top]<b[i])stack[++top]=b[i];
else find(b[i]);
}
printf("%d\n",top);
return 0;
}//lcs,不离散就是lis